\section{Algoritmo Exacto}

% \subsection{Introducci\'on}
% El algoritmo que vamos a presentar en este punto es el que busca la mejor solución al problema de encontrar dos circuitos simples que cubran todos los nodos de un grafo G, que solamente coinciden en un nodo v, y que minimicen la suma de los pesos totales de los dos circuitos.
\subsection{Desarrollo}
Teniendo ya la noción de que \textbf{G} es el grafo sobre el que vamos a trabajar para buscar la solución y que \textit{v} es el nodo donde coinciden los 2 ciclos, vamos a proceder a explicar cómo funciona el algoritmo.

% Lo que nuestro algoritmo exacto hace es partir desde el nodo v y llamar recursivamente en todos los nodos restantes y luego repite esto estando parado en el nuevo nodo teniendo en cuenta las siguientes consideraciones:
El procedimiento de nuestro algoritmo exacto se basa en hacer llamadas recursivas por cada nodo, haciendo una llamada nueva a otro nodo siguiendo las reglas presentadas a continuación:
\begin{compactitem}
\item no continúo con soluciones parcialmente armadas que tengan un peso mayor que el de mi mejor solución obtenida hasta el momento (poda de backtracking).
\item no ir hacia un nodo ya revisado que no sea \textit{v} (nodo origen).
\item no ir hacia el nodo \textit{v} si esta unión no forma un circuito de 3 o más elementos.
\item no ir hacia el nodo \textit{v} si la cantidad de nodos que me quedan sin revisar no me permitirá luego formar un nuevo circuito.
\item no ir hacia el nodo \textit{v} para formar el segundo circuito si me quedan nodos por revisar.
\end{compactitem}

% Una vez que el algoritmo arma una solución válida (una solución que cumple formar 2 circuitos que se unen solo en el nodo v y que pasan por todos los nodos) la agrega a una lista de posibles soluciones para que, luego de agregar todas las posibles soluciones a la lista, evalue cada una de ellas y se quede con la de peso mínimo.
Una vez que el algoritmo llega a formar una solución con 2 circuitos que se unen solo en el nodo \textit{v} y que pasan por todos los nodos, es seguro que esta solución es mejor que la que teníamos antes, ya que sino no habríamos llegado a formar los 2 circuitos con todos los nodos por lo indicado en el primer ítem de las reglas que sigue el algoritmo en el párrafo anterior. Dado esto, como me aseguro de llegar siempre a soluciones mejores que las que ya tenía, al finalizar el algoritmo vamos a tener la mejor de todas las soluciones armadas para este problema.
%%% la agrega a una lista de posibles soluciones y sigue buscando más soluciones. Luego, al tener todas las posibles soluciones en la lista, evalúa cada una de ellas y se queda con la de peso mínimo. El procedimiento paso por paso puede verse en el pseudocódigo.

% Finalmente sabiendo esto es facil darse cuenta que el algoritmo Exacto es un algoritmo de backtracking ya que revisa todas las posibles soluciones que pueden llegar a ser una solución válida para nuestro problema y luego de verificar todas estas se queda con la mejor habiendo realizado pequeños podas en el camino a cada solución armada.
Finalmente, sabiendo esto es fácil darse cuenta que el algoritmo Exacto es un algoritmo de \texttt{backtracking} ya que intenta revisar todas las posibles soluciones que pueden llegar a ser una solución válida para nuestro problema (por las decisiones que se toman en el algoritmo antes de llamar recursivamente) utilizando una poda que evita que construyamos soluciones que seguro no van a ser mejores que la que ya tenemos. 
%%% En nuestro caso, como podrá verse en el pseudocódigo, una vez que forma una solución válida con dos circuitos centrados en \textit{v} y después de haberla agregado a la lista de posibles soluciones, vuelve una cantidad de llamadas recursivas hacia atrás y analiza si agregando otros nodos en un paso dado se puede llegar a una nueva solución válida.%diferente con dos ciclos válidos diferentes a los previamente elegidos.

También es importante aclarar que el algoritmo no verifica si dos ciclos son iguales, simplemente busca todas las posibles combinaciones de nodos que cumplan con los ítems antes nombrados. Un ejemplo para un grafo de 5 nodos y nodo inicial 3 sería : sol A) 3-0-1-3-2-4-3  y sol B) 3-1-0-3-2-4-3 .
Estas dos soluciones viéndolas como un grafo son el mismo, pero nosotros no nos preocuparemos por distinguirlas, aunque si la mejor solución hasta el momento es la A), al formar la solución B), ésta resulte descartada por tener el mismo peso que la anterior (esto sucederá cuando el algoritmo intente agregar el último nodo ya que es cuando los pesos de los dos se vuelven iguales).
\newpage
\subsection{Pseudoc\'odigo}
% Antes de mostrar el pseudocódigo vamos a explicar como está compuesta la clase principal Exacto.
Para resolver el problema disponemos de lo siguiente:

\textit{Nota:En los siguientes arreglos cada posición del mismo corresponde al nodo del mismo valor.}
\begin{compactitem}
% \item \textbf{vector visitados}: Es un arreglo de booleanos el cual va a estar marcado en true o false en cada posición segun si el nodo con ese mismo valor ya fue o no visitado.
\item \textbf{vector\_visitados}: Es un arreglo de booleanos en el cual cada posición va a estar marcada como \texttt{true} o \texttt{false} indicando si el nodo de esta posición ya fue o no visitado, respectivamente
\item \textbf{vector\_solucion}: Es un arreglo de enteros en el cual vamos generando la solución a medida que se va ejecutando el algoritmo. Si consideramos que la cantidad de nodos es \texttt{n}, entonces este arreglo tiene \texttt{n+1} posiciones. El arreglo representa el circuito de una forma no convencional: cada posición representa un nodo y la i-ésima posición apunta al nodo siguiente en el circuito del nodo \textit{i}. De esta forma si partimos del nodo origen \textit{v} al hacer vector\_solucion[v] vamos a estar obteniendo el nodo al cual fuimos inicialmente desde v. Finalmente, la razón por la cual el arreglo tiene \texttt{n+1} elementos es que vamos a partir dos veces desde \textit{v} hacia otro nodo (una sera al inicio y la otra sera luego de formar el primer ciclo) por lo que vamos a guardar en la última posición del arreglo el nodo al cual nos dirijimos luego de formar el primer ciclo.
% \item \textbf{cant nodos}: Es un entero que nos indica la cantidad total de nodos del grafo.
% \item \textbf{nodo origen}: Es un int que representa al nodo desde donde partimos.
% \item \textbf{lista soluciones}: Es una lista de vectores solucion(arreglos de int) que va a ir guardando todas las posibles soluciones que va a ir generando al inicio el algoritmo.
\item \textbf{cant ciclos}: Es un int que va a valer 0 o 1 segun corresponda para poder saber si ya forme un ciclo o no.
% \item \textbf{solucion final}: Es un arreglo de int que va a contener, con el mismo formato que el vector solucion, a la solción final del algoritmo.
\item \textbf{pesoHastaElMomento}: Es un int que mantiene el peso total de la solución formada hasta el momento en el vector\_solucion.
\item \textbf{res}: Es un int que mantiene el peso de la la solución de menor peso armada hasta al momento y al finalizar los algoritmos va a contener el peso de la mejor solución.
\end{compactitem}


\begin{parr}
\begin{algorithm}[H]
\caption{\operMA{Exacto}{ \vin{instance}{InstanceTP3}}}
\begin{algorithmic}[1]\parskip=1mm
\STATE \COMMENT inicializo los atributos de la clase Exacto
\STATE cant\_nodos $\leftarrow$ instance.n
\STATE nodo\_origen $\leftarrow$ instance.nodo\_origen
\STATE vector\_visitados[nodo\_origen] $\leftarrow$ true
\STATE ciclos\_armados $\leftarrow$ 0
\STATE busca\_ciclos\_recursiva(vector\_visitados, vector\_solucion, nodo\_origen, ciclos\_armados, 1)
%%%\STATE solucion\_final $\leftarrow$ la solución con el mínimo peso de las halladas por \texttt{busca\_ciclos\_recursiva}
\end{algorithmic}
Complejidad:
 O(n!) con n igual a la cantidad de nodos del grafo ya que lo complejo de esta función es el llamado a la función busca\_ciclos\_recursiva, donde esta tiene una complejidad de O(n!). Al finalizar este algoritmo, el peso de la solución del problema que queremos resolver queda guardado en el atributo \textit{res} de la clase Exacto y el recorrido que realizó esta queda en \textit{vector\_solucion}.

\end{algorithm}
\end{parr}

\begin{parr}
\begin{algorithm}[H]
\caption{\operMA{busca\_ciclos\_recursiva}{ \vin{vector\_visitados}{boolean[]}, \vin{vector\_solucion}{int[]}, \vin{nodo\_actual}{int}, \vin{ciclos\_armados}{int}, \vin{cantidad\_revisados}{int}}}
\begin{algorithmic}[1]\parskip=1mm
\STATE vector\_visitados[nodo\_actual] $\leftarrow$ true
\FOR {\textit{i} $=$ 0 ; \textit{i} $<$ cant\_nodos ; \textit{i}++}
 \IF{\textit{peso\_hasta\_el\_momento} más peso de ir del \textit{nodo\_actual} hasta \textit{i} es menor al peso de \textit{res}}
  \IF{ ya visité al nodo \textit{i}} % 184
    \IF{  (ciclos\_armados = \texttt{1}) $\wedge$ (nodo\_actual = nodo\_origen)} %187
      \STATE \COMMENT{Si estoy armando el segundo ciclo y el nodo actual es el origen}
      \STATE vector\_solucion[\textit{cant\_nodos}] $\leftarrow$ \textit{i}
	  \STATE pesoHastaElMomento $\leftarrow$ pesoHastaElMomento + peso del eje (nodo\_actual, i);      
      \STATE \begin{small}busca\_ciclos\_recursiva(vector\_visitados, vector\_solucion, \textit{i}, ciclos\_armados, cantidad\_revisados\texttt{+1})                                                                                                                                                          \end{small}
      \STATE pesoHastaElMomento $\leftarrow$ pesoHastaElMomento - peso del eje (nodo\_actual, i); 
      \STATE vector\_solucion[\textit{cant\_nodos}] $\leftarrow$ \texttt{-1}
    \ELSE %194
      \STATE vector\_solucion[\textit{nodo\_actual}] $\leftarrow$ \textit{i}
       \STATE pesoHastaElMomento $\leftarrow$ pesoHastaElMomento + peso del eje (nodo\_actual, i); 
      \STATE \begin{small}busca\_ciclos\_recursiva(vector\_visitados, vector\_solucion, \textit{i}, ciclos\_armados, cantidad\_revisados\texttt{+1})                                                                                                                                                          \end{small}
       \STATE pesoHastaElMomento $\leftarrow$ pesoHastaElMomento - peso del eje (nodo\_actual, i); 
      \STATE vector\_solucion[\textit{nodo\_actual}] $\leftarrow$ \texttt{-1}
    \ENDIF %199
    \STATE vector\_visitados[\textit{i}] $\leftarrow$ \texttt{false}
  \ELSE %202
    \IF {(\textit{i} = nodo\_origen) $\wedge$ $\neg$(nodo\_actual = nodo\_origen)} %205
      \IF {(ciclos\_armados = 0) $\wedge$ (cantidad\_revisados $\leq$ cant\_nodos \texttt{-2}) $\wedge$ (cantidad\_revisados $>$ \texttt{2})} %208
      \STATE \COMMENT{(no visité todavía el nodo \textit{i})$\wedge$(\textit{i} = nodo\_origen $\neq$ nodo\_actual)$\wedge$(estoy en el primer ciclo)$\wedge$ }
      \STATE \COMMENT{(cantidad\_revisados me permite luego armar otro circuito)$\wedge$(el circuito tiene 3 nodos o más)}
	\STATE \textit{var} \textit{tmp} $\leftarrow$ vector\_solucion[\textit{nodo\_actual}]
	\STATE vector\_solucion[\textit{nodo\_actual}] $\leftarrow$ \textit{i}
	 \STATE pesoHastaElMomento $\leftarrow$ pesoHastaElMomento + peso del eje (nodo\_actual, i); 
	\STATE \begin{small}busca\_ciclos\_recursiva(vector\_visitados, vector\_solucion, \textit{i}, ciclos\_armados\texttt{+1}, cantidad\_revisados)	                                                                                                                                                    \end{small}
	 \STATE pesoHastaElMomento $\leftarrow$ pesoHastaElMomento - peso del eje (nodo\_actual, i); 
	\STATE vector\_solucion[\textit{nodo\_actual}] $\leftarrow$ \textit{tmp}
      \ELSE %214
	\IF {(ya armé ambos ciclo) $\wedge$ (revise todos los nodos)}%217
	  \STATE \COMMENT{Tengo una solución válida en el vector solución mejor que la que tenia antes}
	  
\STATE  solucion\_final $\leftarrow$ vector\_solucion
\STATE  res $\leftarrow$ pesoHastaElMomento + peso del eje (nodo\_actual, i)
% 	  \STATE Integer[] nueva\_sol $\leftarrow$ vector\_solucion
% 	  \STATE nueva\_sol[nodo\_actual] $\leftarrow$ i
% 	  \STATE lista\_soluciones.add(nueva\_sol)
%	  \STATE agregar el \textit{vector\_solucion} a la lista de soluciones con el valor \textit{i} en la posición \textit{nodo\_actual}
	\ENDIF %226
      \ENDIF %227
    \ENDIF %228
  \ENDIF %229
 \ENDIF
\ENDFOR %230
\STATE \textbf{return} la lista de soluciones
\end{algorithmic}
Complejidad:
 O(n!) con n igual a la cantidad de nodos del grafo. Esto se debe a que en cualquier caso se entra al \texttt{for} y se lo ejecuta cant\_nodos veces. Luego se puede dar que caiga dentro de los \texttt{if} en una de las llamadas recursivas luego de haber marcado como revisado al nodo actual y por esto al ejecutar la llamada recursiva se va ejecutar el \texttt{for} n veces pero solamente se va a poder llamar recursivamente en n-1 de los n casos(suponiendo que no se produce una poda).
 Por todo esto las llamadas recursivas se podrían dar de la siguiente forma:
\begin{compactitem}
 \item n-1 llamadas recursivas la primera vez 
 \item n-2 llamadas recursivas la segunda vez
 \item n-2 llamadas recursivas la tercera vez(porque puedo llamar recursivamente sobre el nodo\_origen)
 \item n-3 llamadas recursivas la cuarta vez y así continua restando de a 1 hasta que la cantidad de elementos sea n-n+2 (esto para que por lo menos queden 2 nodos los cuales formen el segundo circuito si es que no formé ninguno hasta el momento) como mínima cantidad.
\end{compactitem}
De todas formas, como este algoritmo es de backtraking, la complejidad que se aprecia al correr el algoritmo es menor a O(n!) por la poda realizada que nos evita muchas llamadas recursivas.
\end{algorithm}
\end{parr}


\newpage
\subsection{Complejidad}
Al igual que como se lo explica en el pseudocódigo, la complejidad total de calcular la solución exacta a nuestro problema para un grafo G de n nodos es O(n!). Esto se explica más detalladamente en el mismo, pero en resumidas palabras, se debe a la cantidad de llamadas recursivas que se dan al momento de armar todas los posibles recorridos de dos circuitos que se cruzan en el mismo nodo v.

Finalmente, tiene esa complejidad siempre, ya que siempre va a ejecutar el \texttt{for} principal de la función \texttt{busca\_ciclos\_recursiva}. En otras palabras, siempre se verifican todas las \textit{soluciones posibles} hasta el momento en que se aplica una poda, y como la cantidad de soluciones posibles es siempre la misma para un \textit{n} dado, ya que la cantidad de ejes no cambia y por ende los ciclos formables posibles son los mismos, la complejidad asintótica es siempre la misma. Por ende, el peor caso  sería O(n!).

Es importante destacar que consideramos que puede sucerder que se de el mejor caso si tenemos un grafo con las siguientes caracteristicas:
\begin{compactitem}
\item la primer solución que forma el algoritmo busca\_ciclos\_recursiva dado este grafo es la mejor de todas 
\item cumple que la suma total de los ejes que pertenecen a la mejor solución es menor que el peso de cualquier eje restante que no pertenece a esta.
\end{compactitem}
Esto hace que para cualquier nodo que intente probar agregar ingrese al if de la poda y sea descartada automaticamente (a menos que esté formando mi misma solución pero armando los circuitos en un orden distinto ).
\subsection{Demostración de la solución}

\subsubsection{Terminación:}


En esta sección vamos a tratar las razones por la cual el algoritmo Exacto termina.
Primero podemos decir que este simplemente llama a una función la cual vamos a ver en mas detalle. Esta es busca\_ciclos\_recursiva la cual termina por las siguientes razones:


 \textbf{busca\_ciclos\_recursiva}:



Podemos asegurar que este algoritmo termina ya que en cada llamada recursiva se ingresa a un \textbf{for} que realiza una cantidad limitada de iteraciones y, además, antes de este, se marca al nodo con el que se llamo a la recursión como visitado. Esto último evita realizar llamadas recursivas de forma infinita porque con las guardas de los \textbf{if} me aseguro de distinguir los casos en que esto sucede. 

También para asegurarme terminar y obtener soluciones validas hago que si voy a formar un ciclo, la cantidad de nodos revisados hasta el momento sea mayor a 3, para que si o si el ciclo armado sea de por lo menos 3 nodos, y también me aseguro que me sobren por lo menos 2 nodos sin visitar para poder formar el segundo ciclo.

Luego se distingue el caso en que el nodo a donde voy a ir (o sea el que me indica el for) ya fue revisado. En este caso va a depender si ese nodo es el nodo origen o no, ya que en caso de serlo, si llamo recursivamente sobre el voy a formar un ciclo y, para el caso de no serlo, simplemente no voy a hacer nada.

Otra razon por lo que este algoritmo termina es que una vez que armo el segundo ciclo me guardo la solución en el vector solucion\_final y el peso del camino y no hago nada más. Por esto "vuelve en la recursión" a la función que la llamó y en esta se va a avanzar en el for y se va a continuar iterando sobre los nodos siguientes en caso de haberlos.

Finalmente, por las razones dadas antes, podemos decir que el algoritmo termina ya que la cantidad de llamadas recursivas máximas que este hace son limitadas. Sabemos que por cada llamada recursiva se van a llamar a lo sumo la cantidad de nodos no visitados en nuevas llamadas recursivas y como siempre marco un nodo como visitado al inicio de estas, me evito que esto no termine nunca. 

Por las razones comentadas anteriormente podemos decir que este algoritmo termina en una cantidad limitada de pasos.



\subsubsection{Correctitud:}

Al igual que antes, como se puede apreciar en el pseudocódigo y en el código, el algoritmo Exacto es correcto con respecto a la solución que encuentra. Como esta solución se encarga de obtenerla el algoritmo busca\_ciclos\_recursiva vamos a analizarlo a continuación.
busca\_ciclos\_recursiva se asegura de:
\begin{compactitem}
\item primero forma una solución valida para asignarsela a solucion\_final y a \textit{res} el peso de esta.
\item en base a este nuevo \textit{res} se comienza a formar soluciones de la misma forma que se dijo en la terminación, solo que nos evitamos continuar con soluciones armadas hasta el momento que tengan un mayor peso que el \textit{res} actual.
\item una vez que, luego de varias llamadas recursivas, armo una solución que tiene un menor peso que \textit{res}, entonces este nuevo recorrido se lo asigno a solucion\_final y a \textit{res} le asigno el peso de esta.
\end{compactitem}
Como ya lo explicamos en la terminación, el algoritmo termina. Esto, sumado a los items anteriores, nos asegura que luego de una cantidad finita de iteraciones, si logramos formar una mejor solución, entonces esta va a ser la nueva solución del algoritmo. 
Al finalizar el algoritmo se cumple que ya recorrimos todas las posibles soluciones y nos quedamos con la mejor (por lo dicho antes) y por esto podemos asegurar que este algoritmo termina correctamente dandonos la solución buscada.
Luego podemos decir que el algoritmo Exacto es correcto ya que como busca\_ciclos\_recursiva lo es, y exacto usa este algoritmo, entonces este termina correctamente y nos brinda la solución al problema que nos deja busca\_ciclos\_recursiva en los atributos de Exacto.
%Con lo explicado en la terminación podemos decir que el algoritmo \textit{busca\_ciclos\_recursiva} arma soluciones válidas, con esto me refiero a que este guarda soluciones que cumplen tener 2 circuitos que se unen en un mismo nodo inicial, y por estas razones este algoritmo devuelve una lista de todas las posibles soluciones validas que se pueden generar dado un nodo inicial y un grafo de más de 4 nodos.
%Una vez finalizada la ejecución de este algoritmo se procede a evaluar cada una de estas posibles soluciones en la función \textit{evaluar\_solucion} donde se recorre cada una de estas y se guarda la mejor solución hasta el momento. Esto permite que al momento de finalizar la recorrida de todas las posibles soluciones obtenga el peso de la mejor de todas estas para luego retornarlo como solución final del algoritmo \textit{Exacto}.

%\newpage
%\subsection{Tests y graficos}
% Ante todo vale aclarar que consideramos que no existe un peor caso para el algoritmo exacto. Esto se debe a lo explicado en la sección desarrollo en la que decíamos que el algoritmo arma una lista de todas las posibles soluciones válidas y luego las evalua teniendo en cuenta el peso.
% 
% Esto lo que hace es que cualquiera sea el grafo que se le de al algoritmo, se va a buscar todas las posibles soluciones validas y luego se va a evaluar cada una de estas posibles soluciones para saber cual es la mejor de todas (o sea la que tiene un peso mínimo) y por esta razon para dos grafos cualquiera distintos en sus pesos con n nodos no va a haber uno que tarde más en terminos de complejidad o uno para el cual el algoritmo no funcione, ya que para los dos va a generar las soluciones y al final las va a evaluar.

%Consideramos utilizar solamente un generador de grafos random para testear %el algoritmo alcanza para verificar su buen funcionamiento.
%el rendimiento del algoritmo.
%
%

%\begin{figure}[H]
%\centering
%\epsfig{file=./graficos/exacto.png,width=0.9\linewidth,clip=}
%\caption{Tests del algoritmo exacto para grafos completos con distribución de pesos aleatorios.}
%\end{figure}
